package com.jack.leetcode.eachProblem07;

/**
 * Created by zhang_j on 2020/7/15
 */
public class 不同的二叉搜索树 {

    public static void main(String[] args) {
        System.out.println(numTrees(1));
        System.out.println(numTrees(2));
        System.out.println(numTrees(3));
        System.out.println(numTrees(4));
        System.out.println(numTrees(5));
        System.out.println(numTrees(6));
        System.out.println(numTrees(7));
    }

    public static int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2;i <= n;i++){
            int sum = 0;
            for(int j = 0;j < i/2;j++){
                sum += dp[i-1-j] * dp[j];
            }
            sum *=2;
            if(i % 2 == 1){
                sum += dp[i/2] * dp[i/2];
            }
            dp[i] = sum;
        }
        return dp[n];
    }
}
